// Written by Craig'n'Dave
using System;
// Merge sort using recursion method 1
// This version is the classic implementation
namespace ConsoleApp1
{
    class Program
    {
        static string[] merge_sort(string[] items)
        {
            // Split step
            if (items.Length > 1)
            {
                int mid = items.Length / 2;
                // array1 contains the first half of the items
                string[] array1 = new string[mid];
                for (int index = 0; index < mid; index++)
                {
                    array1[index] = items[index];
                }
                // array2 contains the second half of the items
                string[] array2 = new string[items.Length - mid];
                for (int index = mid; index < items.Length; index++)
                {
                    array2[index - mid] = items[index];
                }

                merge_sort(array1);
                merge_sort(array2);

                int index1 = 0;
                int index2 = 0;
                int items_index = 0;

                // Merge step             
                while ((index1 < array1.Length) && (index2 < array2.Length))
                {
                    // Check each item in each list, and add the smallest item to a new list
                    if (string.Compare(array1[index1], array2[index2]) < 0)
                    {
                        items[items_index] = array1[index1];
                        index1 = index1 + 1;
                    }
                    else
                    {
                        items[items_index] = array2[index2];
                        index2 = index2 + 1;
                    }
                    items_index = items_index + 1;
                }

                // Add left over items from the remaining list
                while (index1 < array1.Length)
                {
                    items[items_index] = array1[index1];
                    index1 = index1 + 1;
                    items_index = items_index + 1;
                }

                while (index2 < array2.Length)
                {
                    items[items_index] = array2[index2];
                    index2 = index2 + 1;
                    items_index = items_index + 1;
                }

            }
            return items;
        }

        // Main program starts here
        static void Main(string[] args)
        {
            string[] items = { "Florida", "Georgia", "Delaware", "Alabama", "California" };
            items = merge_sort(items);
            Console.WriteLine(String.Join(", ", items));
        }
    }
}
